package leetcode.day_2020_2021_2_1_2021_2_7;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 31. 下一个排列
 * https://leetcode-cn.com/problems/next-permutation/
 * https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/
 * 思路：
 * 从数组最后往前找到第一个升序序列，保存下标i,j
 * 再从数组最后往前查找到第一个比下标i大的数，并记住下标k
 * 交换i，k的数字
 * 反转下标j到nums.length-1的数字
 * 注意：
 * 1、若数组长度为0或者为1，直接返回
 * 2、若此数组所表示的长度已为最大数字，则直接反转并返回
 */
public class LeetCode0031 {
    public static void main(String[] args) {
        int[] arr = {3, 2, 1};
        nextPermutation(arr);
        System.out.println(Arrays.toString(arr));
        Set<Integer> set = new HashSet<>();
        set.contains(1);
    }

    public static void nextPermutation(int[] nums) {
        if(nums.length == 0 || nums.length == 1) return;
        int i = nums.length - 2;
        int j = nums.length - 1;
        int k = nums.length - 1;
        while (i>=0 && nums[i]>=nums[j]) {
            i--; j--;
        }
        if (i >= 0) {
            while (nums[i] >= nums[k])
                k--;
        } else {
            // 执行到这里，说明此数已是最大数，直接反转并返回
            reverse(j, nums);
            return;
        }

        swap(i, k, nums);
        reverse(j, nums);
    }

    private static void reverse(int j, int[] nums) {
        for (int front=j, end=nums.length-1; front<end; front++, end--) {
            swap(front, end, nums);
        }
    }

    private static void swap(int i, int k, int[] nums) {
        int temp = nums[i];
        nums[i] = nums[k];
        nums[k] = temp;
    }


}
